package cn.zhl.leetcode.队列;

/**
 * @program: demos
 * @description: 循环队列，用数组实现
 * @author: 刘振华
 * @create: 2020-04-10 10:39
 **/
public class CircleQueue<E> {
	private static final int DEFAULT_CAPACITY = 6;
	private int front;
	private int size;
	private E[] elements;
	private int capacity;

	public CircleQueue() {
		capacity = DEFAULT_CAPACITY;
		elements = (E[]) new Object[capacity];
	}

	public static void main(String[] args) {
		CircleQueue<Integer> queue = new CircleQueue<>();
		for (int i = 0; i < 6; i++) {
			queue.enQueue(i);
		}
		System.out.println(queue);
		for (int i = 0; i < 5; i++) {
			queue.deQueue();
		}
		for (int i = 100; i < 120; i++) {
			queue.enQueue(i);
		}
		for (int i = 0; i < 5; i++) {
			queue.deQueue();
		}
//        while (!queue.isEmpty()){
//            System.out.println(queue.deQueueRear());
//            System.out.println(queue.deQueue());
//        }
		System.out.println(queue);

		while (!queue.isEmpty()) {
			System.out.println(queue.deQueue());
		}

	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public void enQueue(E e) {
		ensureCapacity();
		elements[index(size++)] = e;
	}

	public E deQueue() {
		E element = elements[front];
		elements[front] = null;
		front++;
		front %= capacity;
		size--;
		return element;
	}

	public E deQueueRear() {
		int index = index(size - 1);
		E e = elements[index];
		elements[index] = null;
		size--;
		return e;
	}

	public E front() {
		return elements[front];
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("capacity=").append(capacity)
			.append(" size = ").append(size).append(",[");
		for (int i = 0; i < capacity; i++) {
			sb.append(elements[i]).append(",");
		}
		sb.append("]");
		return sb.toString();
	}

	private int index(int index) {
		int rs = index + front;
		return rs >= elements.length ? rs - elements.length : rs;
	}

	/**
	 * 扩容
	 */
	private void ensureCapacity() {
		if (size < capacity) {
			return;
		}
		int oldCapacity = capacity;
		capacity += capacity >> 1;
		System.out.println("=================扩容：从" + oldCapacity + "到" + capacity);
		E[] newElements = (E[]) new Object[capacity];
		for (int i = 0; i < size; i++) {
			newElements[i] = elements[index(i)];
		}
		elements = newElements;
		front = 0;
	}

}
